package Datastruct.Linked;

public class CircleLinked {

    //创建first结点，当前没有编号
    Boy first=new Boy(-1);

    //加入小孩构成环形链表

    public  void addBoy(int nums){
        if(nums<1){
            System.out.println("输入的数据不合理...");
            return;
        }

        //添加辅助结点
        Boy temp=null;

        for(int i=1;i<=nums;i++){

            Boy boy=new Boy(i);

            if(i==1){
                first=boy;
                first.setNext(first);   //行成环状
                temp=first;
            }else {

                temp.setNext(boy);
                boy.setNext(first);
                temp=boy;
            }
        }
    }

    //遍历链表数据
    public  void showList(){
        if(first==null){
            System.out.println("链表为空。。。。。");
            return;
        }

        //第一个结点不能动，因此需要辅助指针 完成遍历
        Boy temp=first;
        while (true){
            System.out.printf("小孩的编号是%d\n",temp.getNo());
            if(temp.getNext()==first){    //最后一个结点指向的是头结点说明遍历完毕
                break;
            }

            //  后移
            temp=temp.getNext();

        }
    }

    /**
     *  startno 表示从第几个孩子开始数数
     *  countNun表示 数几下
     *  nums表示人数个数
     */
    public  void  countBoy(int startNo,int countNum ,int nums){
        if(first==null||startNo<1||startNo>nums){
            System.out.println("参数输入有误，请重新输入参数");
            return;
        }
        //创建一个辅助指针帮助小孩出圈
        Boy  helper=first;         //指向最后一个结点
        while (true){
            if(helper.getNext()==first){  //寿命当前是最后一个结点
                break;
            }
            helper=helper.getNext();
        }
        //报数之间，让first和helper以移动k-1次  first移动到要报数的小孩身上
        for(int j=0;j<startNo-1;j++){
            first=first.getNext();
            helper=helper.getNext();
        }

        //当小孩报数时，让first和helper指针同时移动m-1次
        //循环出圈直到圈中只有一个小孩
        while (true){
            if(helper==first){
                break;
            }
            //让first与helper移动countNum-1次
            for(int j=0;j<countNum-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }
            //first指向的就是要出圈小孩的结点
            System.out.printf("小孩%d出圈\n",first.getNo());

            //first指向的小孩出圈
            first=first.getNext();
            //将尾指针执行指向下一个开始报数的小孩
            helper.setNext(first);
        }


        System.out.println("最后出圈的小孩是:"+first.getNo());
    }

}
